import java.util.Comparator;

public class BinarySearch<T> {

    private Comparator<T> comparator;

    public BinarySearch(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    /**
     * 递归实现
     *
     * @param array 数组
     * @param key   元素
     * @return 索引
     */
    public int search_recu(T[] array, T key) {
        return search_recu(array, key, 0, array.length);
    }

    /**
     * 递归实现
     *
     * @param array 数组
     * @param key   元素
     * @param low   开始索引
     * @param high  结束索引
     * @return 索引
     */
    public int search_recu(T[] array, T key, int low, int high) {
        if (high - low < 1) {
            return -1;
        }

        int mid = low + ((high - low) >> 1);
        T midElement = array[mid];
        int compareResult = comparator.compare(key, midElement);
        if (compareResult < 0) {
            return search_recu(array, key, low, mid);
        } else if (compareResult > 0) {
            return search_recu(array, key, mid + 1, high);
        } else {
            return mid;
        }
    }

    /**
     * 迭代实现
     *
     * @param array 数组
     * @param key   元素
     * @return 索引
     */
    public int search_iter(T[] array, T key) {
        int low = 0;
        int high = array.length;

        while (low < high) {
            int mid = low + ((high - low) >> 1);
            T midElement = array[mid];
            int compareResult = comparator.compare(key, midElement);
            if (compareResult < 0) {
                high = mid;
            } else if (compareResult > 0) {
                low = mid + 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

}
